Search Results

Documents authored by Çağırıcı, Onur


Document
Recognizing H-Graphs - Beyond Circular-Arc Graphs

Authors: Deniz Ağaoğlu Çağırıcı, Onur Çağırıcı, Jan Derbisz, Tim A. Hartmann, Petr Hliněný, Jan Kratochvíl, Tomasz Krawczyk, and Peter Zeman

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)


Abstract
In 1992 Biró, Hujter and Tuza introduced, for every fixed connected graph H, the class of H-graphs, defined as the intersection graphs of connected subgraphs of some subdivision of H. Such classes of graphs are related to many known graph classes: for example, K₂-graphs coincide with interval graphs, K₃-graphs with circular-arc graphs, the union of T-graphs, where T ranges over all trees, coincides with chordal graphs. Recently, quite a lot of research has been devoted to understanding the tractability border for various computational problems, such as recognition or isomorphism testing, in classes of H-graphs for different graphs H. In this work we undertake this research topic, focusing on the recognition problem. Chaplick, Töpfer, Voborník, and Zeman showed an XP-algorithm testing whether a given graph is a T-graph, where the parameter is the size of the tree T. In particular, for every fixed tree T the recognition of T-graphs can be solved in polynomial time. Tucker showed a polynomial time algorithm recognizing K₃-graphs (circular-arc graphs). On the other hand, Chaplick et al. showed also that for every fixed graph H containing two distinct cycles sharing an edge, the recognition of H-graphs is NP-hard. The main two results of this work narrow the gap between the NP-hard and 𝖯 cases of H-graph recognition. First, we show that the recognition of H-graphs is NP-hard when H contains two distinct cycles. On the other hand, we show a polynomial-time algorithm recognizing L-graphs, where L is a graph containing a cycle and an edge attached to it (which we call lollipop graphs). Our work leaves open the recognition problems of M-graphs for every unicyclic graph M different from a cycle and a lollipop.

Cite as

Deniz Ağaoğlu Çağırıcı, Onur Çağırıcı, Jan Derbisz, Tim A. Hartmann, Petr Hliněný, Jan Kratochvíl, Tomasz Krawczyk, and Peter Zeman. Recognizing H-Graphs - Beyond Circular-Arc Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{agaoglucagirici_et_al:LIPIcs.MFCS.2023.8,
  author =	{A\u{g}ao\u{g}lu \c{C}a\u{g}{\i}r{\i}c{\i}, Deniz and \c{C}a\u{g}{\i}r{\i}c{\i}, Onur and Derbisz, Jan and Hartmann, Tim A. and Hlin\v{e}n\'{y}, Petr and Kratochv{\'\i}l, Jan and Krawczyk, Tomasz and Zeman, Peter},
  title =	{{Recognizing H-Graphs - Beyond Circular-Arc Graphs}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.8},
  URN =		{urn:nbn:de:0030-drops-185420},
  doi =		{10.4230/LIPIcs.MFCS.2023.8},
  annote =	{Keywords: H-graphs, Intersection Graphs, Helly Property}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail